Description of Prior Art
A graph is mathematically defined as a set of nodes with a set of edges that connect the nodes. A graph can be visually represented using a diagram, which depicts the edges as lines or other connecting devices between the nodes.
Graphs and diagrams have been used throughout history to represent the relationship among concepts or objects. They have been used to depict the relationships among people (family trees, organization charts) and scientific or mathematical knowledge (chemical reaction diagrams, Feynman diagrams in particle physics). As technology advanced, the use of graphs and diagrams become more common as a means of capturing the interaction among parts of complex systems (schematic diagrams for circuits, flowcharts for computer software).
In the 1980s, the spread of personal computers made it easier for individuals to quickly produce their own graphs and diagrams. By the mid 1990s, a type of graph called a concept map achieved a modest amount of popularity as a means of capturing and understanding the relationship among concepts, ideas, or things.
In U.S. Pat. No. 5,506,937 to Ford (1996), concept maps play a significant role. In this system, a user interface is described for browsing knowledge contained within an expert system. The browsing interface consists of a concept map with nodes that depict various objects corresponding to concepts in the domain being explored. The concept map places nodes that represent related concepts close together, with explicitly drawn links between concepts.
The user can interact with the nodes to open a window with more details about the node's concept. The details may be an image, an audio or video recording, or a more detailed textual display of the node. The details may also be another concept map, in which case the new concept map appears in a new window where the user can interact with it.
There are several drawbacks to the Ford method. The concept maps used in the Ford system are static diagrams that must be authored by a knowledge engineer. This authoring includes the layout of the nodes on the concept map. Because the nodes are in a fixed position on the concept map, the system cannot dynamically rearrange the map in response to user actions. Furthermore, the nodes depicted on the concept map only display a title or a few key words describing each node. To see more details about a node, the user must open an additional window on top of the concept map. This additional window partially obscures the concept map.
Another drawback is caused by the display of nodes and relationships statically on a two-dimensional surface. This makes depicting highly non-hierarchical graphs (graphs with significant cross-links among its nodes) difficult, because a highly non-hierarchical network of nodes will not map onto a two-dimensional surface without significant inaccuracies in the mapping. In order to perform such a mapping, the system needs to prioritize the information being displayed, both by prioritizing particular nodes in the network, and also by prioritizing the links connecting the nodes. Concept maps do not prioritize either the nodes or the links. Without such priorities, graph layout decisions are difficult to make.
Several improvements to the static concept map approach have been proposed over the past several years. The simplest of these are based on the interactive layout of the nodes surrounding a currently selected node. These selected-node layouts provide a solution to the problem of prioritizing the nodes: the currently selected node has the highest priority. Other nodes have decreasing priority based on how many links removed they are from the selected node. This aids in traversing non-hierarchical graphs by creating a local hierarchy centered on the currently selected node.
U.S. Pat. No. 6,256,032 to Hugh (2001) describes a selected-node user interface. This user interface has a relatively pre-defined layout for the nodes that is designed for navigating a primarily hierarchical graph. The currently selected node is placed at the center of the graph. Children of the currently selected node are arranged in a grid below it. The parent of the currently selected node is displayed above and to the right of it, and the siblings are displayed in a list to the right of the parent.
A second list to the left of the parent is used to display nodes that are cross-linked (non-hierarchically linked) to the currently selected one. This provides some degree of non-hierarchical navigation, but it does so by imposing a local hierarchy around the selected node.
The Hugh method was designed to work with two windows. One of the windows displays the actual graph with the currently selected node at the center. The second window displays a more detailed version of the currently selected node. Like the Ford method, the Hugh method depicts the nodes on the graph with only a short title or keywords. As the user selects a new node, the display shifts to place that node at the center, and its parent, siblings, and children assume their appropriate positions. Simultaneously, the second window displays detailed information about the selected node.
The selected node paradigm is more flexible than the static map approach of the Ford method. By allowing the user to select a current node, the system can interactively adjust the graph in response to the users input. However, this response is fairly simplistic, allowing only selection of one node at a time. For instance, suppose that the user has selected a node recently, but it is not currently the selected node. The fact that it had been selected recently will play no role in determining the position or size of the node. Only the number of links from the currently selected node is important in determining the position and size.
U.S. Pat. No. 6,300,957 to Rao et. al. (2001) is another selected-node layout method that uses a hyperbolic mapping to arrange other nodes around the currently selected one. This is effective because the hyperbolic mapping provides more space for nodes that are closer to the currently selected one. This method has been implemented by Inxight, Inc., of Santa Clara, Calif., in their Cyberbolic display. FIG. 1 shows the user interface to the Cyberbolic display.
As the user selects a node in the Rao method, that node assumes the center position in the graph. Other nodes are arranged around the selected node, based on the number of connections to the selected node. Nodes that are one link away from the selected node are displayed on a ring immediately surrounding the selected node; nodes that are two links away are displayed on a ring outside the first one, etc. As the nodes get further away from the selected node, the rings get closer together and the nodes (as displayed on the graph) get smaller due to the hyperbolic mapping.
The advantage of this system is that more screen area is given to nodes close to the selected node, which presumably hold more interest to the user than nodes further from the selected node. However, the selected-node mechanism utilized by the Rao method is just as limited as that used by the Hugh method. And like the Ford and Hugh methods, the only information presented for each node is a short title or a few keywords.
All three of these systems lack the ability to utilize prioritization information to assist in the user interaction. Such prioritization information can come from the user interactions, or it can come from values stored with the graph. This additional prioritization information can then be utilized by the graph layout procedure to determine an optimal layout, given the priorities for the nodes and the priorities for the links connecting the nodes.
A mathematical mechanism of utilizing such priorities during node layout has been known for many years. In the early 1980s, the mathematician Teuvo Kohonen devised a theory to explain the development of connections in a neural network, called the self-organizing map. This mechanism accounts for the physical proximity of neurons with similar response properties in biological neural networks. Mathematically, the theory proposes an energy function for the entire neural network consisting of contributions from pairs of neurons. The energy function is formulated so that if two similar neurons are close together, the energy will be lower than if they are further apart.
Development in this model proceeds by modifying the positions of nodes within the neural network so as to minimize the energy function, resulting in a mapping that places similar neurons near each other. Using Kohonen's construction, it is possibly to construct a graph layout algorithm that determines optimal placements of nodes given a set of priorities on the links connecting the nodes.
Kohonen's work is primarily concerned with the automated generation of static maps. No provisions are made for user interactions that might dynamically change the maps. Additionally, Kohonen's original formulation incorporated prioritization information for the connections between the nodes in the neural network, but it did not incorporate priorities on the nodes themselves. However, additional layout constraints can be included through suitable modification of the energy function.
ThinkMap, by Plumb Design of New York, N.Y., is a graph-based user interface that appears to use a variant of Kohonen's self-organizing map to layout its nodes. FIG. 2a shows the user interface to this system. It is a selected-node layout like the Rao method and the Hugh method, but it exhibits more flexibility in its layouts. For instance, some nodes can be displayed with more space surrounding them than others. It is not clear whether this additional space is used to emphasize nodes that have been assigned a higher priority. If this is the use, then the node prioritization scheme is limited in that no changes in the priority of the nodes appear to occur during user interaction. Like the other two selected-node interfaces, it provides limited information about the nodes on the graph itself, instead using a second window to display more details about the currently selected node.
ThinkMap is better able to traverse non-hierarchical graphs than either the Hugh method or the Rao method. However, lacking true node and link prioritization, the map can quickly becomes tangled if the links are highly non-hierarchical. This is illustrated in FIG. 2b. 
In conclusion, the drawbacks of the prior art are:
                1) The simplistic mechanism for node selection provides limited user input to the graph layout mechanisms        2) The presentation of nodes on the graph provides limited information about each node, requiring a second window to be opened to display more details about a node        3) The absence of prioritization information for both nodes and links makes the layout mechanisms simplistic and unable to handle complex non-hierarchical relationships among the nodes.        